#!/usr/bin/env python
#-*- coding: utf-8 -*-
#__author__:vincentlc
#time: 16/4/9 : 22:40



'''
Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
'''


# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None:
            return head
        point1 = head
        point2 = head.next
        point3 = None
        if point2.next == None:
            point1.next = point2.next
            point2.next = point1
            head = point2
        while point2!= None and point2.next != None:
            point3 = point2.next
            point2.next = point1
            point1.next = point3
            point1 = point3
            point2 = point1.next
        return head

    def swapPairs2(self,head):
        if head == None or head.next==None:
            return head

        tmp1 = head.next
        tmp2 = self.swapPairs(tmp1.next)
        tmp1.next = head
        head.next = tmp2

        return tmp1



